﻿//1191. K 次串联后最大子数组之和
//给定一个整数数组 arr 和一个整数 k ，通过重复 k 次来修改数组。
//例如，如果 arr = [1, 2] ， k = 3 ，那么修改后的数组将是[1, 2, 1, 2, 1, 2] 。
//返回修改后的数组中的最大的子数组之和。注意，子数组长度可以是 0，在这种情况下它的总和也是 0。
//由于 结果可能会很大，需要返回的 109 + 7 的 模 。


class Solution {
public:
    int kConcatenationMaxSum(vector<int>& arr, int k)
    {
        const int MOD = 1000000007;

        if (arr.empty())
            return 0;

        long long maxOfEnd = arr[0] > 0 ? arr[0] : 0;
        long long maxSoFar = maxOfEnd;
        long long sum = arr[0];

        for (int i = 1; i < min(k, 2) * arr.size(); ++i) {
            maxOfEnd = std::max(maxOfEnd + arr[i % arr.size()], static_cast<long long>(arr[i % arr.size()]));
            maxSoFar = std::max(maxOfEnd, maxSoFar);
            if (i < arr.size()) sum += arr[i];
        }

        if (sum > 0 && k > 2) {
            long long remainder = (sum * (k - 2)) % MOD;
            maxSoFar += remainder;
        }

        return static_cast<int>(maxSoFar % MOD);
    }
};